package com.leetcode;

public class ThreeSumClosest
{
	public int threeSumClosest(int[] num, int target)
	{
		// Start typing your Java solution below
		// DO NOT write main() function
		bubbleSort(num);
		int min = num[0] + num[1] + num[num.length - 1];// 第一组数作为最小值来处理
		int sum;
		for (int i = 0; i < num.length - 2; i++)
		{
			int a = num[i];
			if (i != 0 && a == num[i - 1])
			{// 去重:首项重复
				continue;
			}
			int k = i + 1;
			int n = num.length - 1;
			while (k < n)
			{
				int b = num[k];
				int c = num[n];
				if (n < num.length - 1 && c == num[n + 1])
				{// 去重:尾项重复
					n--;
					continue;
				}
				if (a + b + c == target)
				{
					return target;
				}
				sum = a + b + c;
				if (Math.abs(sum - target) < Math.abs(min - target))
				{// 比较是否更靠近target
					min = sum;
					n--;
					continue;
				}
				if (sum > target)
				{// 单纯判断即可
					n--;
				}
				else
				{
					k++;
				}
			}
		}
		return min;
	}

	public void bubbleSort(int[] array)
	{
		if (array.length == 0)
			return;
		for (int i = 0; i < array.length - 1; i++)
		{
			for (int j = 0; j < array.length - i - 1; j++)
			{
				if (array[j] > array[j + 1])
				{
					swap(array, j, j + 1);
				}
			}
		}
	}

	public void swap(int[] array, int i, int j)
	{
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}
